import java.util.Arrays;
import java.util.LinkedList;

// various movement strategies for rogue
class RogueAI extends AI {

    public RogueAI(Map map, Game game) {
        super(map, game);
    }

    @Override
    public int[] move() {
        updatePos();
        return randomMove(game.getRoguePos());
    }
}


// simply move away from the distance of the monster, regardless of map
class RunAway extends RogueAI {

    public RunAway(Map map, Game game) {
        super(map, game);
    }

    @Override
    public int[] move() {
        updatePos();
        int[] direction = map.findDirection(monsterPos, roguePos); // away direction
        if (map.isDirectionMoveable(roguePos, direction)) return direction;
        return new int[]{0, 0};
    }
}


// if there is an accessible loop, go to that loop and live forever
// otherwise, go to the furthest reachable land, while searching for loop.
class LoopElseFurthest extends RogueAI {
    //    private Queue<int[]> pathToLoop;
    private final LinkedList<LinkedList<int[]>> loops;
    private final LinkedList<LinkedList<int[]>> record = new LinkedList<>();
    private final LinkedList<Node> bfsNodes = new LinkedList<>();
    private int targetLoopIndex = -1;
    private final LinkedList<int[]> pathToDoor = new LinkedList<>();
    private boolean inLoop = false;

    public LoopElseFurthest(Map map, Game game) {
        super(map, game);
        updatePos();
        loops = getLoops(bfsNodes);
        for (Node node : bfsNodes) { // find loop lands that must be visited by the rogue in each loop
            int connectedLoop = 0;
            for (int[] neighbor : map.getNeighbors(node.position)) {
                if (containsPosition(bfsNodes, neighbor))
                    connectedLoop++;
            }
            if (connectedLoop <= 3)
                ((bfsNode) node).must = true;
        }
    }

    @Override
    public int[] move() {
        updatePos();

        // check if in a loop, not including open space
        if (!inLoop) {
            for (int i = 0; i < loops.size(); i++) {
                if (containsArray(loops.get(i), roguePos) && ((bfsNode) getNode(bfsNodes, roguePos)).must) {
                    inLoop = true;
                    targetLoopIndex = i;
                    break;
                }
            }
        }

        // already in a loop
        if (inLoop) {
            int furthestFromMonster = Integer.MIN_VALUE;
            int[] goTo = roguePos;
            for (int[] move : map.getNeighbors(roguePos)) {
                if (containsArray(loops.get(targetLoopIndex), move)) {
                    int distance = AStarLength(monsterPos, move, true);
                    if (distance > furthestFromMonster) {
                        furthestFromMonster = distance;
                        goTo = Arrays.copyOf(move, move.length);
                    }
                }
            }
            int[] dir = positionToMove(roguePos, goTo);
            return dir;
        }

        // path to door not found yet, keep looking
        if (pathToDoor.isEmpty()) {
            targetLoopIndex = bfds(loops, record, bfsNodes, pathToDoor); // perform breadth first double search
        }

        // path to door found, go to the door
        if (!pathToDoor.isEmpty()) {
            int[] move = pathToDoor.poll();
            if (pathToDoor.isEmpty())
                inLoop = true;
            return positionToMove(roguePos, move);
        }

        // no door reachable yet, temporarily move to the furthest land.
        LinkedList<int[]> path = AStar(roguePos, record.getLast().getLast(), true);
        if (path.size() > 1) return positionToMove(roguePos, path.get(1));

        return new int[]{0, 0}; // no place to go, stay and die
    }
}


// Go to the furthest reachable land
class GoFurthest extends RogueAI {
    private final LinkedList<LinkedList<int[]>> record = new LinkedList<>();

    public GoFurthest(Map map, Game game) {
        super(map, game);
    }

    @Override
    public int[] move() {
        updatePos();
        bfds(new LinkedList<>(), record);
        LinkedList<int[]> path = AStar(roguePos, record.getLast().getFirst(), true);
        if (path.size() > 1) return positionToMove(roguePos, path.get(1));
        return new int[]{0, 0}; // no place to go, stay and die
    }
}